[HNOI2004] L语言

Description

给定一个由 n 个字符串 s 组成的字典,再给定 m 句话 t ,求每句话在该字典下可以理解的最长前缀。
n20,m50,s10,t2×106n\leq 20,m\leq 50,|s|\leq 10,|t|\leq 2\times 10^6

Solution

阅读全文 »

[HAOI2009] 求回文串

Description

给定长度为 n 的字符串 s ,每次只能交换相邻两个位置。求使得 s 为回文串的最小交换次数。无解输出 -1 。
n106n\leq 10^6,保证都是大写字母

Solution

阅读全文 »

PAM 学习笔记

回文自动机(PAM)是针对给定串,包含了该串所有回文子串的信息的自动机。
PAM 的每个节点代表了一个本质不同的回文子串,记 s[p] 为点 p 代表的回文子串。
PAM 的每个节点有三个基础属性:fail/len/child 。
len:a[p].len 表示 s[p] 的长度。

阅读全文 »

Query on a tree VI

Description

给你一棵 nn 个点的树,每个点为黑色或白色。要求维护两个操作:

ABC163F path pass i

Description

给定一棵 nn 个点的树,树上每个点有一个颜色。对于每一种颜色,求有多少无向路径至少经过一次该颜色。
n105n\leq 10^5

Solution

阅读全文 »

OI 回忆录

有一个夜晚我烧毁了所有的记忆,从此我的梦就透明了。有一个早晨我扔掉了所有的昨天,从此我的脚步就轻盈了。


阅读全文 »

Atcoder Regular Contest 107 题解

Pro A Simple Math

题意:给定 a,b,ca,b,c ,求 i=1aj=1bk=1ci×j×k(mod998244353)\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}\sum\limits_{k=1}^{c}i\times j\times k\pmod{998244353} 的值。

数据范围:1a,b,c1091\leq a,b,c\leq10^9

简单的提取公因式可得原式等价于求 i=1aij=1bjk=1ck\sum\limits_{i=1}^{a}i\sum\limits_{j=1}^{b}j\sum\limits_{k=1}^{c}k

阅读全文 »

Atcoder Regular Contest 106 题解

Pro A 106

题意:给定 nn ,求满足 3a+5b=n3^a+5^b=n 的任意一组解。

数据范围:n1018n\leq 10^{18}

预处理出值在 101810^{18} 次方以内的 33 的幂和 55 的幂然后直接枚举。

阅读全文 »